<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,100分)- 开心消消乐（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>给定一个N行M列的二维矩阵&#xff0c;矩阵中每个位置的数字取值为0或1。矩阵示例如&#xff1a;<br /> 1100<br /> 0001<br /> 0011<br /> 1111<br /> 现需要将矩阵中所有的1进行反转为0&#xff0c;规则如下&#xff1a;<br /> 1&#xff09; 当点击一个1时&#xff0c;该1便被反转为0&#xff0c;同时相邻的上、下、左、右&#xff0c;以及左上、左下、右上、右下8 个方向的1&#xff08;如果存在1&#xff09;均会自动反转为0&#xff1b;<br /> 2&#xff09;进一步地&#xff0c;一个位置上的1被反转为0时&#xff0c;与其相邻的8个方向的1&#xff08;如果存在1&#xff09;均会自动反转为0&#xff1b;</p> 
<p>按照上述规则示例中的矩阵只最少需要点击2次后&#xff0c;所有值均为0。请问&#xff0c;给定一个矩阵&#xff0c;最少需要点击几次后&#xff0c;所有数字均为0&#xff1f;</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行输入两个数字N&#xff0c;M&#xff0c;分别表示二维矩阵的行数、列数&#xff0c;并用空格隔开</p> 
<p>之后输入N行&#xff0c;每行M个数字&#xff0c;并用空格隔开</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>最少需要点击几次后&#xff0c;矩阵中所有数字均为0</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;"> <p>4 4<br /> 1 1 0 0<br /> 0 0 0 1<br /> 0 0 1 1<br /> 1 1 1 1</p> </td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">2</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>用例图示如下</p> 
<p><img alt="" height="273" src="https://img-blog.csdnimg.cn/79b71828f77044ce9f51768aaf82554f.png" width="668" /></p> 
<p>可以发现&#xff0c;只要是连接在一起的1&#xff08;八个方向都算连接&#xff09;&#xff0c;点击任意1个&#xff0c;都会蔓延到相连的其他1。因此&#xff0c;本题重点不在于点击哪个1&#xff0c;而是有多少块连在一起的1。 即孤岛问题&#xff0c;求解不连通的岛屿数量。孤岛问题可以使用并差集求解。</p> 
<p>本题类似于<a href="https://fcqian.blog.csdn.net/article/details/127606569" rel="nofollow" title="LeetCode - 200 岛屿数量_伏城之外的博客-CSDN博客">LeetCode - 200 岛屿数量_伏城之外的博客-CSDN博客</a></p> 
<p>题解可以看这个博客。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
let n, m;
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 1) {
    [n, m] &#61; lines[0].split(&#34; &#34;).map(Number);
  }

  if (n &amp;&amp; lines.length &#61;&#61;&#61; n &#43; 1) {
    lines.shift();
    const matrix &#61; lines.map((line) &#61;&gt; line.split(&#34; &#34;));
    console.log(getResult(matrix, n, m));
    lines.length &#61; 0;
  }
});

function getResult(matrix, n, m) {
  const ufs &#61; new UnionFindSet(n * m);

  // 八个方向的偏移量
  const offset &#61; [
    [-1, -1],
    [-1, 0],
    [-1, 1],
    [0, -1],
    [0, 1],
    [1, -1],
    [1, 0],
    [1, 1],
  ];

  for (let i &#61; 0; i &lt; n; i&#43;&#43;) {
    for (let j &#61; 0; j &lt; m; j&#43;&#43;) {
      if (matrix[i][j] !&#61; &#34;1&#34;) {
        ufs.count--;
        continue;
      }
      for (let k &#61; 0; k &lt; offset.length; k&#43;&#43;) {
        const [offsetX, offsetY] &#61; offset[k];
        const newI &#61; i &#43; offsetX;
        const newJ &#61; j &#43; offsetY;

        if (
          newI &gt;&#61; 0 &amp;&amp;
          newI &lt; n &amp;&amp;
          newJ &gt;&#61; 0 &amp;&amp;
          newJ &lt; m &amp;&amp;
          matrix[newI][newJ] &#61;&#61; &#34;1&#34;
        ) {
          ufs.union(i * m &#43; j, newI * m &#43; newJ);
        }
      }
    }
  }

  return ufs.count;
}

class UnionFindSet {
  constructor(n) {
    this.fa &#61; new Array(n).fill(0).map((_, i) &#61;&gt; i);
    this.count &#61; n;
  }

  find(x) {
    if (x !&#61;&#61; this.fa[x]) {
      return (this.fa[x] &#61; this.find(this.fa[x]));
    }
    return x;
  }

  union(x, y) {
    const x_fa &#61; this.find(x);
    const y_fa &#61; this.find(y);

    if (x_fa !&#61;&#61; y_fa) {
      this.fa[y_fa] &#61; x_fa;
      this.count--;
    }
  }
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc &#61; new Scanner(System.in);

        int n &#61; sc.nextInt();
        int m &#61; sc.nextInt();

        int[][] matrix &#61; new int[n][m];
        for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
            for (int j &#61; 0; j &lt; m; j&#43;&#43;) {
                matrix[i][j] &#61; sc.nextInt();
            }
        }

        System.out.println(getResult(matrix, n, m));
    }

    public static int getResult(int[][] matrix, int n, int m) {
        UnionFindSet ufs &#61; new UnionFindSet(n * m);

        // 八个方向的偏移量
        Integer[][] offsets &#61; {
                {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}
        };

        for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
            for (int j &#61; 0; j &lt; m; j&#43;&#43;) {
                if (matrix[i][j] !&#61; 1) {
                    ufs.count--;
                    continue;
                }

                // 不要紧张&#xff0c;这里固定循环8次&#xff0c;不会造成O(n^3)
                for (Integer[] offset : offsets) {
                    int newI &#61; i &#43; offset[0];
                    int newJ &#61; j &#43; offset[1];

                    if (newI &gt;&#61; 0 &amp;&amp; newI &lt; n &amp;&amp; newJ &gt;&#61; 0 &amp;&amp; newJ &lt; m &amp;&amp; matrix[newI][newJ] &#61;&#61; 1) {
                        ufs.union(i * m &#43; j, newI * m &#43; newJ);
                    }
                }
            }
        }

        return ufs.count;
    }
}

// 并查集
class UnionFindSet {
    int[] fa;
    int count;

    public UnionFindSet(int n) {
        this.fa &#61; new int[n];
        this.count &#61; n;
        for (int i &#61; 0; i &lt; n; i&#43;&#43;) this.fa[i] &#61; i;
    }

    public int find(int x) {
        if (x !&#61; this.fa[x]) {
            return (this.fa[x] &#61; this.find(this.fa[x]));
        }
        return x;
    }

    public void union(int x, int y) {
        int x_fa &#61; this.find(x);
        int y_fa &#61; this.find(y);

        if (x_fa !&#61; y_fa) {
            this.fa[y_fa] &#61; x_fa;
            this.count--;
        }
    }
}</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 并查集
class UnionFindSet:
    def __init__(self, n):
        self.fa &#61; [idx for idx in range(n)]
        self.count &#61; n

    def find(self, x):
        if x !&#61; self.fa[x]:
            self.fa[x] &#61; self.find(self.fa[x])
            return self.fa[x]
        return x

    def union(self, x, y):
        x_fa &#61; self.find(x)
        y_fa &#61; self.find(y)

        if x_fa !&#61; y_fa:
            self.fa[y_fa] &#61; x_fa
            self.count -&#61; 1


n, m &#61; map(int, input().split())

matrix &#61; []
for i in range(n):
    matrix.append(list(map(int, input().split())))

ufs &#61; UnionFindSet(n * m)

# 八个方向的偏移量
offsets &#61; ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))

for i in range(n):
    for j in range(m):
        if matrix[i][j] !&#61; 1:
            ufs.count -&#61; 1
            continue

        for offsetX, offsetY in offsets:
            newI &#61; i &#43; offsetX
            newJ &#61; j &#43; offsetY

            if 0 &lt;&#61; newI &lt; n and 0 &lt;&#61; newJ &lt; m and matrix[newI][newJ] &#61;&#61; 1:
                ufs.union(i*m&#43;j, newI*m&#43;newJ)

print(ufs.count)
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>